package com.kehao.leetcode.jzoffer;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author Kehao.Chen
 * @version 1.0
 * @date 2022/6/14 18:54
 */
public class JZSolution017 {
    public String minWindow(String s, String t) {
        String result = "";
        int length = Integer.MAX_VALUE;
        char[] tCharArray = t.toCharArray();
        char[] sCharArray = s.toCharArray();
        Set<Character> tSet = new HashSet<>();
        Map<Character, Integer> sMap = new HashMap<>();
        for (int i = 0; i < tCharArray.length; i++) {
            tSet.add(tCharArray[i]);
        }
        int left = 0;
        for (; left < sCharArray.length; left++) {
            if (tSet.contains(sCharArray[left])) {
                break;
            }
        }
        if (s.length() - left < t.length()) {
            return "";
        }
        int right = left;
        while (sMap.size() < tSet.size()&&right<s.length()) {
            if(tSet.contains(sCharArray[right])){
                Integer count = sMap.get(sCharArray[right]);
                count = count ==null?0:count;
                sMap.put(sCharArray[right],count+1);
                right ++;
            }
        }
        if(sMap.size() < tSet.size()){
            return "";
        }else{
            left = right - length;
            result = s.substring(left,right);
        }
        while (sMap.size() < tSet.size()&&right<s.length()){
            char leftChar = s.charAt(left);
            while (sMap.get(leftChar)>1){
                if(tSet.contains(sCharArray[right])){
                    Integer count = sMap.get(sCharArray[right]);
                    count = count ==null?0:count;
                    sMap.put(sCharArray[right],count+1);
                    right ++;
                }
            }
        }
        if(sMap.size() < tSet.size()){
            return "";
        }else{
            left = right - length;
            result = s.substring(left,right);
        }


        return result;
    }


}
